/**
 * 449. 序列化和反序列化二叉搜索树
 * https://leetcode.cn/problems/serialize-and-deserialize-bst/
 */
const { createTreeNode, TreeNode, displayTreeNode } = require('../../libs/public');

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  if (!root) {
    return '';
  }
  let result = '';
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    result += `,${node.val}`;
    if (node.right) {
      stack.push(node.right);
    }
    if (node.left) {
      stack.push(node.left);
    }
  }
  return result.substr(1);
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  if (!data) {
    return null;
  }

  /**
   * @param {number[]} nums
   * @param {number} begin
   * @param {number} end
   * @return {TreeNode}
   */
  function dfs(nums, begin, end) {
    if (begin > end - 1) {
      return null;
    }
    const rootVal = nums[begin];
    const root = new TreeNode(rootVal);
    let leftEnd = begin + 1;
    while (leftEnd < end && nums[leftEnd] < rootVal) {
      leftEnd += 1;
    }
    root.left = dfs(nums, begin + 1, leftEnd);
    root.right = dfs(nums, leftEnd, end);
    return root;
  }

  const nums = data.split(',').map((s) => parseInt(s, 10));
  return dfs(nums, 0, nums.length);
}

console.log(serialize(createTreeNode([2, 1, 3])) === '2,1,3');
console.log(displayTreeNode(deserialize('2,1,3')) === '[2,1,3]');
console.log(displayTreeNode(deserialize(serialize(null))) === '[]');
